/*
 * @Date: 2021-09-12 19:21:05
 * @Author: Acckno1
 * @LastEditTime: 2021-09-12 19:22:52
 * @Description: 
 */
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;


int tag, radix;
string s1, s2;

// char转十进制的数字
int charToInt(char c) {
    if(c >= '0' && c <= '9') return c - '0';
    if (c >= 'a' && c <= 'z') return c - 'a' + 10;
    
}
// 找到令两个数值相等的进制数。
LL calcTenRadix(string n1, int radix) {
    LL r = 1;
    LL res = 0;
    for (int i = n1.size() - 1; i >= 0; i -- ) {
        int mod = charToInt(n1[i]);
        res += r * mod;
        r = r * radix;
    }
    return res;
}

int solution(string s1, string s2, int tag, int radix) {
    if (tag == 2) return solution(s2, s1, 1, radix);
    
    // n1 转换成10进制
    LL n1 = calcTenRadix(s1, radix);
    // cout << n1 << endl;
    LL l = 0, r = n1 + 1;
    
    for (auto c : s2) l = max(l, (LL)charToInt(c) + 1);
    
    while (l <= r) {
        LL mid = (l + r) >> 1;
        LL t = calcTenRadix(s2, mid);
        if (t >= n1 || t < 0) r = mid - 1;
        else if (t < n1) l = mid + 1;

    }
    if (calcTenRadix(s2, l) == n1) return l;
    return -1;
}

int main() {
    cin >> s1 >> s2 >> tag >> radix;
    int t = solution(s1, s2, tag, radix);
    if (t == -1) 
        puts("Impossible");
    else
        printf("%d\n", t);
    return 0;
}